package easy

/*
时间复杂度:O(MN) 网格的长和宽
空间复杂度:O(MN)
 */

type pair struct {
	x int
	y int
}

var dir = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func islandPerimeter(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	var dfs func(x, y int)
	dfs = func(x, y int) {
		// 一开始只对grid值为1的节点调用dfs,当该节点四个方向上为边界或为水域(即grid值为0)时,说明该块陆地的周长在这个方向是可累加的
		if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0 {
			ans++
			return
		}

		if grid[x][y] == 2 {
			return
		}
		grid[x][y] = 2

		for _, d := range dir {
			dfs(x+d.x, y+d.y)
		}
	}

	for i, rows := range grid {
		for j, v := range rows {
			// 只对陆地进行dfs
			if v == 1 {
				dfs(i, j)
			}
		}
	}
	return ans
}
